#include "NiceMergeSolver.hpp"
#include <algorithm>
#include <cmath>

void    NiceMergeSolver::execute() EXC_THROWER()
{
    EXC_RETHROW_BEGIN()
    {
        // faire un merger, mais au lieu de faire un fusion left-right, right-left
        // creer des couples et faire de la recherche locale sur ces couples
        // notamment avec le basicRandomOrOpt et le randomOpt2
        // il faut aussi coder swap & eventuellement shift
        
		unsigned	merged_tournee = 0;
		unsigned	i = 0;
		unsigned	k = 0;
        unsigned    iteration = 0;
        unsigned    amelioration = 0;
        unsigned    amelioration_iteration = 0;
        unsigned    insert_iteration = 0;
        bool        insert_active = true;
        unsigned    ra = 0;
		SolutionEval    soleval;
        SolutionEval    solevalbest;
        Solution        tmpsol = nmSolution;
        std::multimap<unsigned, unsigned> tournees_by_size;
        std::multimap<double, unsigned> tournees_by_wait;
        std::multimap<unsigned, unsigned>::iterator   it;
        std::multimap<unsigned, unsigned>::reverse_iterator   ir;
        std::multimap<double, unsigned>::reverse_iterator       iw;
        
        Solution    bestsol = nmSolution;
		//nmSolution.clear();

		// insertion
		//std::cout << "insertion" << std::endl;
		
        random_shuffle(nmBase.begin(), nmBase.end());
		// 
        for (i = 0 ; i < nmBase.size() ; i++)
        {
            nmSolution[i].insertClient(Tournee::INSERT_BEGIN, nmBase[i]);
            nmSolution.validateTournee(i);
        }
		//std::cout << "complete" << std::endl;
		bestsol = nmSolution;
		bestsol.eval(&solevalbest);
		
		// complete solution
		if (!nmSolution.isComplete())
			nmSolution.complete();
		
		i = 0;
		
		std::cout << nmSolution.toString() << std::endl;
		
		//std::cout << "core" << std::endl;
        for (;; iteration++)
        {
            if ((iteration - amelioration_iteration) >= nmMaxIt)
                break;
            
            ra = 2 + (rand() % 3);
            
            for (unsigned k = 1 ; k < ra ; k++)
            {
                for (unsigned i = 0 ; i < soleval.seNTournees ; i += (1 << k))
                {
                    //std::cout << nmSolution.toString() << std::endl;
                    
                    if ((i + ((k == 0) ? 1 : (1 << (k - 1)))) >= 100)
                        break;
                    
                    Tournee&	left = nmSolution[i + 0];
                    Tournee&	right = nmSolution[i + ((k == 0) ? 1 : (1 << (k - 1)))];
                    
                    //basicVND(left, right);
					//localVND(left, right, MIN((iteration - amelioration_iteration), (unsigned)((double)soleval.seNTournees * 5.4)));
                    localVND(left, right, MIN(((iteration - amelioration_iteration)), 10));
                    //localVND3(left, right);
                    //localVND(left, right, 5);
                    //localVND(left, right, 1);
                    //localVND2(left, right, 2);
                    nmSolution.validateTournee(i);
                    nmSolution.validateTournee(i + ((k == 0) ? 1 : (1 << (k - 1))));
                }
                
                if ((k % 2) == 0)
                {
					//nmSolution.shuffle();
					//nmSolution.reorganize();
					//nmSolution.shift();
                }
                else
                {
                    //nmSolution.shuffle();
                    //std::cout << nmSolution.toString() << std::endl;
					nmSolution.reorganizeBySizeCouples();
                    
                    //std::cout << nmSolution.toString() << std::endl;
                    //getchar();
                }
                //nmSolution.shift();
           }   
                
                
                // nmSolution.reorganize();
                //
            
            
            nmSolution.eval(&soleval);
            
            
            if (soleval < solevalbest)
            {
				//std::cout << "coucou" << std::endl;
                amelioration++;
                amelioration_iteration = iteration;
                insert_iteration = iteration;
                bestsol = nmSolution;
                solevalbest = soleval;
                std::cout << bestsol.toString() << std::endl;
                std::cout << solevalbest.toString() << std::endl;
                std::cout << "amelioration " << amelioration << "@" << iteration << std::endl;
                //getchar();
                //nmSolution.shuffle();
                //nmSolution.reorganize();
            }
            //else if (false)
            else if (insert_active && ((iteration - insert_iteration) > (iteration - amelioration_iteration)))   // essayer de casser la tournee plus intelligemment
            {
                /*nmSolution.shift();
                nmSolution.reorganize();
                
                
                
                for (unsigned i = 0 ; i < 1 ; i++)
                {
                    unsigned    n_tournee = nmSolution.getEmptyRandomTournee();
                    unsigned    r_tournee;
                    unsigned    r_client = rand() % 100;
                    
                    std::list<unsigned>     clients;
                    
                    r_tournee = nmSolution.getTourneeByClient(r_client);
                    
                    Tournee&    erase = nmSolution[r_tournee];
                    Tournee&    insert = nmSolution[n_tournee];
                    
                    
                    clients.push_back(r_client);
                    
                    while (r_client != DEPOT)
                    {
                        r_client = erase.getSuccessorOf(r_client);
                        clients.push_back(r_client);
                    }
                    
                    clients.pop_back();
                    
                    for (std::list<unsigned>::iterator it = clients.begin() ; it != clients.end() ; ++it)
                    {
                        erase.erase(*it);
                        insert.insertClient(Tournee::INSERT_END, *it);
                    }
                    
                    nmSolution.validateTournee(r_tournee);
                    nmSolution.validateTournee(n_tournee);
                    insert_iteration = iteration;
                    nmSolution.swapTournees(n_tournee, nmSolution.getEmptyRandomTournee());
                
                    nmSolution.reorganize();
                }
                */
                                
                nmSolution = bestsol;
                
                for (unsigned i = 0 ; i < 1 ; i++)
                {
                    unsigned    n_tournee;
                    unsigned    r_tournee;
                    unsigned	client;
                    unsigned	n;
                    unsigned	k;
                    unsigned    r;
                    
                    //tournees_by_size.clear();
                    nmSolution.buildTourneeByWait(tournees_by_wait);
                    
                    r = rand() % tournees_by_wait.size();
                    
                    iw = tournees_by_wait.rbegin();
                    
                    for (n = 0 ; n < r ; ++iw)
                    {
                        r_tournee = iw->second;
                        k = nmSolution[r_tournee].getNbClients();
                    
                        //r_tournee = nmSolution.getFilledRandomTournee();
                        
                        nmSolution.validateTournee(r_tournee);
                        for (unsigned l = 0 ; l < k ; l++)
                        {
                            client = nmSolution[r_tournee].getPredecessorOf(DEPOT);
                            
                            nmSolution.validateTournee(r_tournee);
                            
                            if (client == DEPOT)
                                break;
                            
                            n_tournee = nmSolution.getEmptyRandomTournee();
                            
                            nmSolution[r_tournee].erase(client);
                            nmSolution[n_tournee].insertClient(Tournee::INSERT_END, client);
                            nmSolution.validateTournee(r_tournee);
                            nmSolution.validateTournee(n_tournee);
                        }
                    }
                    
                    //nmSolution.shift();
                    //nmSolution.reorganizeBySizeCouples();
                    insert_iteration = iteration;
                }
                
                nmSolution.eval(&solevalbest);
                soleval = solevalbest;
                bestsol = nmSolution;
                
            }
            else
            {
                //nmSolution = bestsol;
                
                for (unsigned i = 0 ; i < MIN((iteration - amelioration_iteration), soleval.seNTournees) ; i++)
                {
                    unsigned    r = nmSolution.getFilledRandomTournee();
                    unsigned    n = nmSolution.getFilledRandomTournee();
                    
                    nmSolution.swapTournees(r, n);
                }
                //nmSolution.reorganize();
                //nmSolution.shift();
                //nmSolution.shuffle();
                //nmSolution.reorganize();
				//nmSolution.reorganizeBySizeCouples();*/
                //nmSolution.shuffle();
            }
                
        }
        
        nmSolution = bestsol;
        nmSolution.reorganize();
		soBestSolution = &nmSolution;
        
    }
    EXC_RETHROW_END()
}
